package 数据结构与算法.排序算法;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr ={4,6,8,5,9};
        heapSort(arr);
    }

    public static void heapSort(int[] arr){
        int temp;
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr,i,arr.length);
        }

        //将堆顶元素与末尾元素交换，将最大元素沉到数组末端
        //重新调整结构，使其满足堆定义，反复执行调整+交换步骤
        for (int j = arr.length-1; j > 0; j--) {
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
        System.out.println(Arrays.toString(arr));
    }

    //将一个数组（二叉树），调整成一个大顶堆
    /**
     * @param arr   待调整的数组
     * @param i 非叶子节点在数组中的索引
     * @param len   对多少个元素继续调整
     */
    public static void adjustHeap(int[] arr,int i,int len){
        int temp=arr[i];//先取出当前元素的值，保存在临时变量
        for (int k = i*2+1; k < len; k=k*2+1) {
            if (k+1<len&&arr[k]<arr[k+1]){//说明左子结点值小于右子结点值
                k++;//k指向右子结点
            }
            if (arr[k]>temp){//子结点大于父结点
                arr[i]=arr[k];//把较大值赋给当前结点
                i=k;
            }else{
                break;
            }
        }
        //当for循环结束后，已经将以i为父结点树的最大值放在了顶部（局部）
        arr[i]=temp;
    }
}
